package binarySearchTree

import (
	"fmt"
	. "local/algorithm/util"
)

func main() {
	root := Generate([]int{1, 2, 3})
	DeleteNode(root, 3)
	fmt.Println(root)
}

// func Generate(arr []int) *TreeNode {
// 	//[5,3,6,2,4,null,7]
// 	root := &TreeNode{Val: 5}
// 	root.Left = &TreeNode{Val: 3}
// 	root.Right = &TreeNode{Val: 6}
// 	root.Left.Left = &TreeNode{Val: 2}
// 	root.Left.Right = &TreeNode{Val: 4}
// 	root.Right.Right = &TreeNode{Val: 7}
// 	return root
// }

func Generate(arr []int) *TreeNode {
	var root *TreeNode
	for _, v := range arr {
		if root == nil {
			root = &TreeNode{Val: v}
		} else {
			Insert(root, &TreeNode{Val: v})
		}
	}

	return root
}

func Search(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return root
	}
	if val == root.Val {
		return root
	} else if val < root.Val {
		return Search(root.Left, val)
	} else {
		return Search(root.Right, val)
	}
}
func Insert(root *TreeNode, node *TreeNode) {
	if node.Val == root.Val {
		return
	} else if node.Val < root.Val {
		if root.Left == nil {
			root.Left = node
		} else {
			Insert(root.Left, node)
		}
	} else {
		if root.Right == nil {
			root.Right = node
		} else {
			Insert(root.Right, node)
		}
	}
}

func DeleteNode(root *TreeNode, key int) *TreeNode {
	// 查找
	// 查到找后，判断是否单子树节点
	// 双子树节点

	if root == nil {
		return nil
	}

	if key < root.Val {
		root.Left = DeleteNode(root.Left, key)
		return root
	}

	if key > root.Val {
		root.Right = DeleteNode(root.Right, key)
		return root
	}

	// 到这里意味着root.Val==key
	if root.Left == nil {
		new_root := root.Right
		// root.Right = nil
		return new_root
	}

	if root.Right == nil {
		new_root := root.Left
		// root.Left = nil
		return new_root
	}

	successor := minimum(root.Right)
	// successor.Left = root.Left // 这里必须生成新节点successor_copy，对原节点执行successor.Left=root.Left会改变原有树结构，另外下一步会对该节点进行删除
	// successor.Right = minimum(root.Right)
	successor_copy := &TreeNode{Val: successor.Val}
	successor_copy.Left = root.Left
	successor_copy.Right = remove_min(root.Right)
	// root.Right = nil
	// root.Left = nil
	return successor_copy
}

// 删除最小的 返回第二小的节点
func remove_min(root *TreeNode) *TreeNode {
	if root.Left == nil {
		tmp := root.Right
		// root.Right = nil
		return tmp
	} else {
		root.Left = remove_min(root.Left)
		return root
	}
}

// 找出最小的节点
func minimum(root *TreeNode) *TreeNode {
	for root.Left != nil {
		root = root.Left
	}

	return root
}
